public class Test {
    //递归求N的阶乘
    public static int fact(int n) {
        if(n == 1) {
            return 1;
        }
        return n * fact(n-1);//递:上半部分 归：返回下半部分 要有开始条件
    }
    public static void main1(String[] args) {
        //递归：大事化小 小事化了
        //递归的必要条件：1.将原问题分解为子问题（子问题必须与原方法解决办法相同）
        //2.要有出口（开始或结束语句） 否则会造成栈溢出问题
    int ret = fact(5);
        System.out.println(ret);
    }

    //打印1 2 3 4
    public static void print(int n) {
        if(n < 10) {//为个位数
            System.out.print(n);
            return;
        }
        print(n / 10);//不断递归 直到变为结束条件
        System.out.print(n % 10);
    }
    public static void main2(String[] args) {
    print(123);
    }
//递归求 1+2+3+... +10
    public static int sum(int n) {
        if(n == 1) {
            return 1;
        }
        return n + sum(n - 1);
    }
    public static void main3(String[] args) {
        int sum = sum(10);
        System.out.println(sum);
    }
//求一个数之和 例如1729
    public static int sumevery(int n) {
        if(n < 10) {//开始条件
            return n;
        }
        return n % 10 + sumevery(n / 10);//获取个位 / 10 进入下一个递归
    }
    public static void main4(String[] args) {
        System.out.println(sumevery(123));
    }

    //求斐波那契第n项 递归法
    public static int fib(int n) {
        if(n == 1 || n == 2) {
            return 1;
        }

        return fib(n - 1) + fib(n - 2);//第n项等于 前两项之和
    }
    public static void main5(String[] args) {
        System.out.println(fib(1));
        System.out.println(fib(2));
        System.out.println(fib(5));
        System.out.println(fib(40));
    }

//汉诺塔问题
    public static void move(char pos1,char pos2) {
        System.out.print(pos1 + "->" + pos2 + " ");
    }
    public  static void hanoi(int n,char pos1,char pos2,char pos3) {
        if(n == 1) {//只有一个时 A->C
            move(pos1,pos3);
            return;//要返回
        }
        hanoi(n - 1,pos1,pos3,pos2);//挪动n-1个到b
        move(pos1,pos3);//最后一个到C
        hanoi(n - 1,pos2,pos1,pos3);//挪动n-1到c
    }
    public static void main6(String[] args) {
    hanoi(3,'A','B','C');
    }

    public static void main(String[] args) {
        //数组：存储相同类型数据集合 数据类型[] 数组名 = new 数据类型[数组个数]
        //定义方法
        int[] arr1 = new int[]{1,2,3,4,5};
        int[] arr2 = {1,2,3,4,5};//静态初始化
        int[] arr3 = new int[5];//动态初始化
        // 默认初始化值为0
        // 引用类型默认为null
        // 储存类型必须相同
        //空间是连续的
        //初始值下标为0
        //求长度
        System.out.println(arr1.length);
    }
}
